package Hot100.Medium.String_2Pointer.String;

public class LC208_TrieTree {
    public static class TreeNode{
        boolean isEnd = false; // 该节点是否是一个串的结束
        TreeNode[] childNode = new TreeNode[26];
    }

    private final TreeNode root = new TreeNode();

    public void insert(String word){
        TreeNode cur = root;
        for(int c : word.toCharArray()){
            c = c - 'a';// 把字符映射为0-25之间的索引，用于访问childnode[]数组
            if(cur.childNode[c] == null){
                cur.childNode[c] = new TreeNode();
            }
            cur = cur.childNode[c];
        }
        cur.isEnd = true;
    }

    public boolean search(String word){
        return find(word) == 2;
    }

    public boolean startsWith(String prefix){
        return find(prefix) != 0;
    }

    private int find(String word) {
        TreeNode cur = root;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (cur.childNode[c] == null) { // 道不同，不相为谋
                return 0;
            }
            cur = cur.childNode[c];
        }
        // 走过同样的路（2=完全匹配，1=前缀匹配）
        return cur.isEnd ? 2 : 1;
    }
}
